package leetcode.string;

/**
 * @author Cheng Jun
 * Description: 实现strStr()函数。
 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。
 * 如果不存在，则返回 -1 。
 *
 * 说明：
 * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * 对于本题而言，当 needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
 *
 * 链接：https://leetcode.cn/problems/implement-strstr
 * @version 1.0
 * @date 2022/3/1 12:22
 */
public class strStr {

    public static void main(String[] args) {
        System.out.println(strStr("mississippi", "issip"));
    }

    // 暴力算法：时间复杂度 O(m*n)
    public static int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        if (needle.length() > haystack.length()) return -1;
        // bb aa
        outer:
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(0)) {
                int j = 0;
                while (j < needle.length()) {
                    if (haystack.charAt(i + j) != needle.charAt(j++)) continue outer;
                }
                return i;
            }
        }
        return -1;
    }

    // kmp 算法：时间复杂度 O(m+n) https://www.zhihu.com/question/21923021/answer/281346746

}
